package com.leetcode.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * 示例1：
 * 输入：[3,2,3]
 * 输出：3
 * 示例2：
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 * 进阶：
 * 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmz79t/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年08月31日 16:07
 */
class Code169 {

    public static void main(String[] args) {
        int[] nums = {2,3,2,1,3,2,2,1,1,1,1,1,1,1,1};
        int i = majorityElement3(nums);
        System.out.println(i);
    }
    public static int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        int max = 0;
        int count = 1;
        int target = nums[0];
        for (int i=1;i<nums.length;i++){
            if(nums[i] == nums[i-1]){
                count++;
            }else {
                if(max < count){
                    target = nums[i-1];
                    max = count;
                }
                count = 1;
            }
        }
        if(max < count){
            target = nums[nums.length-1];
        }
        return target;
    }

    /**
     * Hash算法
     */
    public static int majorityElement2(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int max = 0;
        int target = 0;
        for (int num : nums){
           if(map.containsKey(num)){
               map.put(num,map.get(num)+1);
           }else {
               map.put(num,1);
           }
        }
       for(Map.Entry<Integer,Integer> entry : map.entrySet()){
           if(entry.getValue()>max){
               max = entry.getValue();
               target = entry.getKey();
           }
       }
        return target;
    }
    /**
     * Boyer-Moore 投票算法
     */
    public static int majorityElement3(int[] nums) {
        Integer count = 0;
        Integer candidate = null;
        for (int num : nums) {
            candidate = count == 0 ? num : candidate;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}
